package com.alex.statistics.method.clusterAnalysis;


import com.alex.statistics.pojo.request.clusterAnalysis.KMeansRequest;
import com.alex.statistics.pojo.result.clusterAnalysis.KMeansResult;
import org.springframework.stereotype.Service;

import java.util.*;

@Service
public class KMeansService {

    public KMeansResult cluster(KMeansRequest request) {
        long startTime = System.currentTimeMillis();

        // 参数校验
        validateRequest(request);

        // 数据准备
        List<double[]> data = request.getData();
        int k = request.getK();
        int maxIterations = request.getMaxIterations();
        double tolerance = request.getTolerance();

        // 当k=0时，使用手肘法自动确定最佳聚类数
        if (k == 0) {
            k = determineOptimalK(data, request.getMaxK());
        }

        // 初始化质心
        List<double[]> centroids = initializeCentroids(data, k);

        // K-Means迭代
        List<Integer> clusterLabels = new ArrayList<>(Collections.nCopies(data.size(), -1));
        boolean changed = true;
        int iteration = 0;

        while (changed && iteration < maxIterations) {
            changed = assignPointsToClusters(data, centroids, clusterLabels);
            updateCentroids(data, clusterLabels, centroids, k);
            iteration++;
        }

        // 计算聚类评估指标
        double inertia = calculateInertia(data, clusterLabels, centroids);

        // 构建结果
        KMeansResult result = new KMeansResult();
        result.setClusterLabels(clusterLabels);
        result.setCentroids(centroids);
        result.setIterations(iteration);
        result.setInertia(inertia);
        result.setComputeTime(System.currentTimeMillis() - startTime);

        return result;
    }

    private int determineOptimalK(List<double[]> data, int maxK) {
        // 使用手肘法确定最佳K值
        List<Double> inertias = new ArrayList<>();
        for (int k = 1; k <= Math.min(maxK, data.size()); k++) {
            List<double[]> centroids = initializeCentroids(data, k);
            List<Integer> labels = new ArrayList<>(Collections.nCopies(data.size(), -1));
            assignPointsToClusters(data, centroids, labels);
            inertias.add(calculateInertia(data, labels, centroids));
        }

        // 计算手肘点
        double maxDiff = 0;
        int optimalK = 2;
        for (int i = 1; i < inertias.size() - 1; i++) {
            double diff = inertias.get(i-1) - inertias.get(i);
            if (diff > maxDiff) {
                maxDiff = diff;
                optimalK = i + 1;
            }
        }
        return optimalK;
    }

    private List<double[]> initializeCentroids(List<double[]> data, int k) {
        // 使用K-Means++算法初始化质心
        Random random = new Random();
        List<double[]> centroids = new ArrayList<>();
        centroids.add(data.get(random.nextInt(data.size())).clone());

        while (centroids.size() < k) {
            List<Double> distances = new ArrayList<>();
            double totalDistance = 0.0;

            // 计算每个点到最近质心的距离
            for (double[] point : data) {
                double minDistance = Double.MAX_VALUE;
                for (double[] centroid : centroids) {
                    double distance = euclideanDistance(point, centroid);
                    minDistance = Math.min(minDistance, distance);
                }
                distances.add(minDistance);
                totalDistance += minDistance;
            }

            // 根据距离选择下一个质心
            double randomValue = random.nextDouble() * totalDistance;
            double cumulativeDistance = 0.0;
            for (int i = 0; i < data.size(); i++) {
                cumulativeDistance += distances.get(i);
                if (cumulativeDistance >= randomValue) {
                    centroids.add(data.get(i).clone());
                    break;
                }
            }
        }
        return centroids;
    }

    private boolean assignPointsToClusters(List<double[]> data, List<double[]> centroids, List<Integer> clusterLabels) {
        boolean changed = false;
        for (int i = 0; i < data.size(); i++) {
            double[] point = data.get(i);
            int closestCentroid = -1;
            double minDistance = Double.MAX_VALUE;

            for (int j = 0; j < centroids.size(); j++) {
                double distance = euclideanDistance(point, centroids.get(j));
                if (distance < minDistance) {
                    minDistance = distance;
                    closestCentroid = j;
                }
            }

            if (clusterLabels.get(i) != closestCentroid) {
                clusterLabels.set(i, closestCentroid);
                changed = true;
            }
        }
        return changed;
    }

    private void updateCentroids(List<double[]> data, List<Integer> clusterLabels, List<double[]> centroids, int k) {
        // 初始化新质心
        List<double[]> newCentroids = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            newCentroids.add(new double[data.get(0).length]);
        }
        int[] counts = new int[k];

        // 计算每个簇的中心点
        for (int i = 0; i < data.size(); i++) {
            int cluster = clusterLabels.get(i);
            double[] point = data.get(i);
            for (int j = 0; j < point.length; j++) {
                newCentroids.get(cluster)[j] += point[j];
            }
            counts[cluster]++;
        }

        // 更新质心
        for (int i = 0; i < k; i++) {
            if (counts[i] > 0) {
                for (int j = 0; j < newCentroids.get(i).length; j++) {
                    newCentroids.get(i)[j] /= counts[i];
                }
            }
            centroids.set(i, newCentroids.get(i));
        }
    }

    private double calculateInertia(List<double[]> data, List<Integer> clusterLabels, List<double[]> centroids) {
        double inertia = 0.0;
        for (int i = 0; i < data.size(); i++) {
            double[] point = data.get(i);
            int cluster = clusterLabels.get(i);
            inertia += Math.pow(euclideanDistance(point, centroids.get(cluster)), 2);
        }
        return inertia;
    }

    private double euclideanDistance(double[] p1, double[] p2) {
        double sum = 0.0;
        for (int i = 0; i < p1.length; i++) {
            sum += Math.pow(p1[i] - p2[i], 2);
        }
        return Math.sqrt(sum);
    }

    private void validateRequest(KMeansRequest request) {
        if (request.getData() == null || request.getData().isEmpty()) {
            throw new IllegalArgumentException("数据不能为空");
        }
        if (request.getMaxK() <= 0) {
            throw new IllegalArgumentException("最大聚类数必须大于0");
        }
        if (request.getMaxIterations() <= 0) {
            throw new IllegalArgumentException("最大迭代次数必须大于0");
        }
        if (request.getTolerance() < 0) {
            throw new IllegalArgumentException("容差值不能为负");
        }
    }
}    